package com.test.daily.leetcode.y2022.m07.day0728.v03;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/28 下午 02:13
 * @version: 1.0
 */
public class Solution {
    public static int whoWin1(int[] arr) {
        int p1 = f1(arr, 0, arr.length - 1);
        int p2 = g1(arr, 0, arr.length - 1);
        return Math.max(p1, p2);
    }

    public static int f1(int[] arr, int L, int R) {
        if (L == R) {
            return arr[L];
        }
        int p1 = arr[L] + g1(arr, L + 1, R);
        int p2 = arr[R] + g1(arr, L, R - 1);
        return Math.max(p1, p2);
    }

    public static int g1(int[] arr, int L, int R) {
        if (L == R) {
            return 0;
        }
        int p1 = arr[L] + f1(arr, L + 1, R);
        int p2 = arr[R] + f1(arr, L, R - 1);
        return Math.min(p1, p2);
    }

    public static int whoWin2(int[] arr) {
        int N = arr.length;
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                fmap[i][j] = -1;
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                gmap[i][j] = -1;
            }
        }
        int p1 = f2(arr, 0, arr.length - 1, fmap, gmap);
        int p2 = g2(arr, 0, arr.length - 1, fmap, gmap);
        return Math.max(p1, p2);
    }

    public static int f2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) {
        if (fmap[L][R] != -1) {
            return fmap[L][R];
        } else if (L == R) {
            fmap[L][R] = arr[L];
        } else {
            int p1 = arr[L] + g2(arr, L + 1, R, fmap, gmap);
            int p2 = arr[R] + g2(arr, L, R + 1, fmap, gmap);
            fmap[L][R] = Math.max(p1, p2);
        }
        return fmap[L][R];
    }

    public static int g2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) {
        if (gmap[L][R] != -1) {
            return gmap[L][R];
        } else if (L == R) {
            gmap[L][R] = 0;
        } else {
            int p1 = arr[L] + f2(arr, L + 1, R, fmap, gmap);
            int p2 = arr[R] + f2(arr, L, R - 1, fmap, gmap);
            gmap[L][R] = Math.min(p1, p2);
        }
        return gmap[L][R];
    }

    public static int whoWin3(int[] arr) {
        int N = arr.length;
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];
        for (int i = 0; i < N; i++) {
            fmap[i][i] = arr[i];
        }
        for (int startCol = 0; startCol < N; startCol++) {
            int L = 0;
            int R = startCol;
            while (R <= startCol) {
                fmap[L][R] = Math.max(arr[L] + gmap[L + 1][R], arr[R] + gmap[L][R - 1]);
                gmap[L][R] = Math.min(arr[L] + fmap[L][R], arr[R] + fmap[L][R]);
                L++;
                R++;
            }
        }
        return Math.max(fmap[0][N - 1], gmap[0][N - 1]);
    }

}
